<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>字节算法题</title>
</head>
<body>
  <script>
    // 1. 栈模拟队列 剑指offer09
    // class CQueue{
    //   constructor(){
    //     this.inStack = [];
    //     this.outStack = [];
    //   }
    //   appendTail(value){
    //     this.inStack.push(value);
    //   }
    //   deleteHead(){
    //     if(!this.outStack.length){
    //       if(!this.inStack.length){
    //         return -1;
    //       }
    //     }
    //     this.in2out()
    //     return this.outStack.pop();
    //   }
    //   in2out(){
    //     while(this.inStack.length){
    //       this.outStack.push(this.inStack.pop());
    //     }
    //   }
    // }

    // 2. 合并两个有序数组，要求O(m+n)
    // var merge = function(nums1, m, nums2, n) {
    // let nums3 = []
    // let p1 = 0
    // let p2 = 0
    // while(nums3.length < m+n){
    //     while(p1 < m && p2 < n){
    //         if(nums1[p1] < nums2[p2]){
    //             nums3.push(nums1[p1++])
    //         }else{
    //             nums3.push(nums2[p2++])
    //         }
    //     }
    //     while(p1 < m){
    //         nums3.push(nums1[p1++])
    //     }
    //     while(p2 < n){
    //         nums3.push(nums2[p2++])
    //     }
    // }
    // for (let i = 0; i != m + n; ++i) {
    //     nums1[i] = nums3[i];
    // }
    // };

    // 3. 最长无重复子串
  //   var lengthOfLongestSubstring = function (s) {
  //     let arr = [], max = 0;
  //     for (let i = 0; i < s.length; i++) {
  //         console.log(s[i])
  //         let index = arr.indexOf(s[i]);
  //         if(index !== -1){
  //             arr.splice(0,index+1)
              
  //         }
  //         arr.push(s.charAt(i))
  //         max = Math.max(arr.length,max)
  //     }
  //     return max
  // };

    // 4. LRU缓存
    // var LRUCache = function(capacity){
    //   this.capacity = capacity;
    //   this.map = new Map();
    // }
    // LRUCache.prototype.get = function(key) {
    //   if(this.map.has(key)){
    //     let temp = this.map.get(key);
    //     this.map.delete(key);
    //     this.map.set(key,temp);
    //     return temp
    //   }else{
    //     return -1
    //   }
    // }
    // LRUCache.prototype.put = function(key,value){
    //   if(this.map.has(key)){
    //     this.map.delete(key);
    //   }
    //   this.map.set(key,value);
    //   if(this.map.size > this.capacity){
    //     this.map.delete(this.map.keys().next().value)
    //   }
    // }

    // 5.二叉树层序遍历
    // var levelOrder = function(root){
    //   if(!root) return [];
    //   const items = [];
    //   const queue = [root,null];
    //   let levelNodes = [];

    //   while(queue.length){
    //     const temp = queue.shift()
    //     if(temp){
    //       levelNodes.push(temp.val)
    //       if(temp.left){
    //         queue.push(temp.left)
    //       }
    //       if(temp.right){
    //         queue.push(temp.right)
    //       }
    //     }else{
    //       items.push(levelNodes);
    //       levelNodes = [];
    //       if(queue.length > 0){
    //         queue.push(null)
    //       }
    //     }
    //   }
    //   return items
    // }

    // 6.最短路径和
    // var minPathSum = function(grid) {
    //   let m = grid.length,n=grid[0].length;
    //   let dp = new Array().fill(0)
    //   dp[0] = grid[0][0]
    //   for(let i = 0;i < m; i++){
    //       for(let j = 0; j < n; j++){
    //           if(i === 0 && j !== 0){
    //               dp[j] = grid[i][j]+dp[j-1]
    //           }else if(i !== 0 && j === 0){
    //               dp[j] = grid[i][j] + dp[j]
    //           }else if(i !== 0 && j !== 0){
    //               dp[j] = grid[i][j]+Math.min(dp[j],dp[j-1])
    //           }
    //       }
    //   }
    //   return dp[n-1]
    // };

    // 7.排列组合
    // var combine = function(n, k){
    //   let res = []
    //   let com = []
    //   const backTrack = (n,k,startIndex) => {
    //     if(com.length === k){
    //       res.push([...com])
    //       return;
    //     }
    //     for(let i = startIndex;i <= n; i++){
    //       com.push(i)
    //       backTrack(n,k,i+1)
    //       com.pop()
    //     }
    //   }
    //   backTrack(n,k,1)
    //   return res
    // }

    // 8.接雨水（横着、竖着）

    // 9.数组分割
    // var partitionDisjoint = function(nums){
    //   let pos = 0;
    //   let max = nums[0];
    //   let leftmax = nums[0];
    //   for(let i =0; i< nums.length;i++){
    //     max = Math.max(max,nums[i]);
    //     if(nums[i] < leftmax){
    //       leftmax =max;
    //       pos = i;
    //     }
    //   }
    //   return pos +1
    // }

    // 10.查找重复元素：找出数组中重复出现过的元素（不考虑返回顺序）
    // var findDuplicates = function(nums){
    //   if(nums.length <= 1) return [];
    //   let hash = new Map();
    //   let items = [];
    //   for(let i = 0;i<nums.length;i++){
    //     if(!hash.has(nums[i])){
    //       hash.set(nums[i],1);
    //     }else{
    //       let count = hash.get(nums[i])
    //       count++
    //       hash.set(nums[i],count)
    //     }
    //   }
    //   for(let key of hash.keys()){
    //     if(hash.get(key) !== 1){
    //       items.push(key)
    //     }
    //   }
    //   console.log(hash)
    //   return items
    // }
    // console.log(findDuplicates([1,2,4,4,3,3,1,5,3]));

    // 11.
    // R.take(1,['baz','baf','bas'])   ===>  ['baz']
    // R.take(2,['baz','baf','bas'])   ===>  ['baz','baf']
    // R.take(3,['baz','baf','bas'])   ===>  ['baz','baf','bas']
    // R.take(4,['baz','baf','bas'])   ===>  ['baz','baf','bas']
    // R.take(3,'ramda')  ===> 'ram'

    // function take (n,nums){
    //   if(n < nums.length){
    //     return nums.slice(0,n)
    //   }
    //   else{
    //     return nums
    //   }
    // }
    // console.log(take(1,['baz','baf','bas'])) 
    // console.log(take(2,['baz','baf','bas']))
    // console.log(take(3,['baz','baf','bas']))
    // console.log(take(4,['baz','baf','bas']))
    // console.log(take(3,'ramda'))

    // 12.给定一个前半部分升序后半部分降序的数组，写一个函数对其进行去重和升序排序
    // function sortReduplicate(arr){
    //   let fast = 0, slow = arr.length -1;
    //   let res = []
    //   while(fast <= slow){
    //     if(arr[fast] < arr[slow]){
    //       if(res[res.length-1] === arr[fast]){
    //         fast++;
    //         continue;
    //       }
    //       res.push(arr[fast]);
    //       fast++;
    //     }else if(arr[fast] > arr[slow]){
    //       if(res[res.length-1] === arr[slow]){
    //         fast--;
    //         continue;
    //       }
    //       res.push(arr[slow])
    //       slow--;
    //     }else{
    //       res.push(arr[fast]);
    //       fast++;
    //       slow--;
    //     }
    //   }
    //   return res
    // }
    // let arr = [1,1,2,2,3,4,5,4,3,3,2,1]
    // console.log(sortReduplicate(arr))

    // 13题目：输入一个字符串，要求删除其中由相同字符组成的长度大于等于2的子串。
    // 示例：输入"abbbaca"->删掉bbb变成"aaca"->删掉aa，得到结果"ca"
    // 解法一：递归
    // function Reduplicate(arr){
    //   let fast = 1,slow = 0;
    //   let temp;
    //   let brr;
    //   let flag = false
    //   for(var i = 0; i< arr.length-1; i++){
    //     if(arr[i] ===  arr[i+1]){
    //       flag = true
    //       break
    //     }
    //     if(!flag && i === arr.length-2) return arr;
    //   }
    //   while(fast < arr.length && flag){
    //         if(arr[fast] !== arr[slow]){
    //           if(fast - slow >= 2){
    //             let brr = arr.split("")
    //             brr.splice(slow,fast-slow)
    //             Reduplicate(brr.join(""))
    //             break
    //           }
    //           fast++;
    //           slow++;
    //         }else{
    //           fast++
    //         }
    //   }
    // }
    // Reduplicate("abbbaca")

    // 解法二：辅助栈
  //   var removeDuplicates = function(s) {
  //     let res = [];
  //     res.push(s[0])
  //     let fast = 0;
  //     let temp = s[0]
  //     while(fast < s.length){
  //       fast++
  //       if(temp === s[fast]){ 
  //         while(s[fast+1] === temp){fast++}
  //         res.pop()
  //         temp = res[res.length-1]
  //       }else{
  //         temp = s[fast]
  //         res.push(s[fast])
  //       }
  //     }
  //     return res.join("")
  // };
  // console.log(removeDuplicates("abbbaca"))
  
  // 14.找到二叉树中是否存在一条路径有满足节点值加起来为目标值
  // var pathSum = function(root,target){
  //   if(root === null) return [];
  //   let res = [];
  //   const dfs = function(root,path){
  //     if(root.left === null && root.right === null){
  //       path.push(root.val)
  //       if(arrSum(path) === target){
  //         res.push([...path])
  //         return;
  //       }
  //       path.pop()
  //     }
  //     path.push(root.val)
  //     if(root.left){
  //       dfs(root.left,path)
  //       path.pop()
  //     }
  //     if(root.right){
  //       dfs(root.right,path)
  //       path.pop()
  //     }
  //   }
  //   const arrSum = function(arr){
  //     let sum = 0;
  //     for(let i = 0;i<arr.length;i++){
  //       sum += arr[i]
  //     }
  //     return sum
  //   }
  //   dfs(root,[])
  //   return res;
  // }

  // 15.全排列
  // var permute = function(nums){
  //   let res = []
  //   const backTrack = (path) => {
  //     if(path.length === nums.length){
  //       res.push(path)
  //       return;
  //     }
  //     nums.forEach(element => {
  //       if(path.includes(element)) return;
  //       backTrack(path.concat(element));
  //     });
  //   }
  //   backTrack([])
  //   return res
  // }
  // console.log(permute([1,2,3]))


  // 16.连续子数组最大和
  // function maxSubArray(nums){
  //   let max_sum = nums[0];
  //   for(let i = 0; i < nums.length; ){
  //     let sum = 0;
  //     let j = i;
  //     while(sum >= 0 && j < nums.length){
  //       sum += nums[j++];
  //       max_sum = Math.max(max_sum,sum)
  //     }
  //     i = j;
  //   }
  //   return max_sum
  // }
  // console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4])) 

  // var maxSubArray = function(nums){
  //   let pre = 0, max_sum = nums[0]
  //   nums.forEach(item => {
  //     pre = Math.max(pre+item, item)
  //     max_sum = Math.max(max_sum,pre)
  //   });
  //   return max_sum
  // }
  // console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4])) 

  // 17.斐波拉契数列
  // 方法一：尾调用优化
  // var fib = function(n){
  //   const fibImp = function(a,b,n){
  //     if(n === 0){
  //       return a
  //     }
  //     return fibImp(b, (a+b)%1000000007, n-1)
  //   }
  //   return fibImp(0,1,n);
  // }
  // 方法二：数组存储 动态规划
  // var fib = function(n){
  //   if(n < 2){
  //     return n
  //   }
  //   let f = [0,1];
  //   for(let i = 2; i <= n; i++){
  //     f[i] = f[i-1] + f[i + 2]
  //   }
  //   return f[n]
  // }
  // console.log(fib(45))

  // 20. 礼物的最大价值
  // var maxValue = function(grid){
  //     if(!grid.length){
  //       return 0
  //     }
  //     let res = []
  //     for(let i = 0; i <grid.length; i++){
       
  //       res[i] = []
  //       for(let j = 0; j < grid[0].length; j++){
  //         res[i][j] = 0
  //       }
  //     }
  //     let m = 0
  //     for(let i = 0; i < res.length; i++){
  //       m += grid[i][0]
  //       res[i][0] = m
  //     }
  //     let n = 0
  //     for(let j = 0; j < res[0].length; j++){
  //       n += grid[0][j]
  //       res[0][j] = n
  //     }
  //     for(let i = 1; i < grid.length; i++){
  //       for(let j = 1;j < grid[0].length; j++){
  //         res[i][j] = Math.max(res[i-1][j],res[i][j-1])+grid[i][j]
  //       }
  //     }
  //     console.log(res)
  //     return res[grid.length-1][grid[0].length-1]
  //   }
  //   console.log(maxValue([[1,3,1],[1,5,1],[4,2,1]]))

  </script>
</body>
</html>